package com.atguigu.binaryTree;

public class Order {
    class Solution {
        int index = 0;
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            index = postorder.length-1;
            return buildTree(postorder, inorder, 0, inorder.length);
        }


        // index不断在后序遍历中找根节点，每次找完之后，根据找到的根节点将中序遍历分成左右两部分，左侧为根的左子树，右侧为根的右子树
        // 注意：与前序中序还原二叉树不同的是，此次需要先还原右子树

        private TreeNode buildTree(int[] postorder, int[] inorder, int left, int right){
            if(left >= right){
                return null;
            }
            // 创建跟节点
            TreeNode root = new TreeNode(postorder[index]);
            // 在中序遍历结果中找到根的位置
            int rootIdx = left;
            while(rootIdx < right){
                if(inorder[rootIdx] == postorder[index])
                    break;

                rootIdx++;
            }
            index--;
            //[rootIdx+1, right): 右子树中的所有节点
            // 递归创建根的右子树
            root.right = buildTree(postorder, inorder, rootIdx+1, right);
            //[left, rootIdx)：左子树中的所有节点
            // 递归创建根的左子树
            root.left = buildTree(postorder, inorder, left, rootIdx);
            return root;
        }
    }
}
